15-499: Parallel Algorithms (Spring 2009)

Instructor: Guy Blelloch, Office hours: Tue 1:30-2:30PM, WeH 7125
Place/Time: Doherty 1212, TR 12:00PM - 1:20PM.
TA: Harsha Simhadri, email: harshas]AT[cs-cmu-edu, Office hours: Wednesday 4:00-5:00PM, WeH 8303

Course Description: In this course students will learn about parallel algorithms. The emphasis will be on algorithms that can be used on shared-memory parallel machines such as multicore architectures. The course will include both a theoretical component and a programming component. Topics to be covered include: modeling the cost of parallel algorithms, lower-bounds, and parallel algorithms for sorting, graphs, computational geometry, and string operations. The programming language component will include data-parallelism, threads, futures, scheduling, synchronization types, transactional memory, and message passing.

Course Requirements: There will be bi-weekly assignments, two exams (midterm and final), and a final project. Each student will be required to scribe one lecture. Your grade will be partitioned into: 10% scribe notes, 40% assignments, 20% project, 15% midterm, 15% final.

Policies: For homeworks, unless stated otherwise, you can look up material on the web and books, but you cannot look up solutions to the given problems. If you do use material from the web, books or papers outside of the reading list you must cite the source. You can work in groups, but must write up the answers individually. You can either typeset or write up written solutions by hand. If you write them by hand it must be readable by the Professor and TA to be graded. Any programming assignments will be due online. Late assignments (up to 2 days late) will be penalized 25%. We will accept one late assignment with no penalty. Assignment will be due at the beginning of class on the due date.

Scribe Schedule. Download Scribe template

Previous version of the class (Fall 07). We would like to thank the Intel Education Initiative for their generous support for developing this course and donating multi6, the multicore machine used in the course.

Approximate Schedule

Class Date Day Topic Notes
1 Tue Jan 13 Introduction (pdf) Assigned Reading: Parallel Algorithms up to 10.2.3 (inclusive)
2 Thu Jan 15 Parallel Models I (pdf) Assign 1 handed out
Assigned Reading: Parallel Algorithms up through 10.2
3 Tue Jan 20 Parallel Models II (pdf) -
4 Thu Jan 22 General Techniques (pdf) Assign 1 Due.
Assign 2 (algorithms in NESL) handed out (see notes)
Assigned Reading: Parallel Algorithms up through 10.3
5 Tue Jan 27 NESL and Sequences I (pdf) Assignment 1 Solution
6 Thu Jan 29 Sequences II (pdf) -
7 Tue Feb 3 Randomization (pdf) -
8 Thu Feb 5 Sequences III (pdf) Assignment 2 Due.
Assign 3 (Algorithms in Cilk++) handed out (see notes)
9 Tue Feb 10 Cilk++ and Sorting (pdf) Assignment 2 Solution
10 Thu Feb 12 Ordered Sets/Dictionaries (pdf) Assignment 3 Part I Due.
11 Tue Feb 17 TBD -
12 Thu Feb 19 Trees(pdf) Assignment 3 Part II Due.
13 Tue Feb 24 Graphs I (pdf)
14 Thu Feb 26 Graphs II (pdf) Assign 4 handed out
15 Tue Mar 3 Graphs III (pdf) Reading: Luby's Maximal Independent Set
16 Thu Mar 6 Graphs IV (pdf) Assignment 4 Due
Reading: Preflow Push Max Flow
- Tue Mar 10 Midsemester Break -
- Thu Mar 12 Midsemester Break Assignment 4 Solution
17 Tue Mar 17 Midterm Review and Computational Geometry (pdf) -
18 Thu Mar 19 Midterm -
19 Tue Mar 24 Computational Geometry and FFT; Rough draft (pdf) -
20 Thu Mar 26 Pipelining and Futures I Slides from class
21 Tue Mar 31 Scheduling Assignment 5 (Algorithms in OpenMP (notes), and closest pairs) handed out.
Final Project Specification
22 Thu Apr 2 Hadoop and Map Reduce -
23 Tue Apr 7 Asynchronous Algorithms I Final project proposal due.
Notes on Asynchronous Algorithms (Updated April 19th)
24 Thu Apr 9 Asynchronous Algorithms II Assignment 5 due.
25 Tue Apr 14 Asynchronous Algorithms III -
- Thu Apr 16 Carnival -
26 Tue Apr 21 Transactional Memory (pdf) -
27 Thu Apr 23 Intel Threading Building Blocks Assignment 6 (this is not due, but just exercises for the final).
Notes
28 Tue Apr 28 CUDA and MPI -
29 Thu Apr 30 Review Final project due

Reading List:

Other Readings:

Assignment Notes
  • Notes on Assignment 2 (NESL)
  • The NESL Page which includes
  • You might find the following information on NESL helpful: NESL Tour (from class) and the NESL quick reference guide.
  • The work and depth costs for the NESL primitives that you should assume are summarized in the Quick Reference Manual.
  • For implementing the my_pack function in problem 1 you should use the cond_put(vals,indices,flags,dest) function. In this function the vectors indices, flags, and vals are all the same length. It writes the values in vals to the locations indices only if the corresponding flag in flags is true. These all get written into the destination vector dest.

  • Notes on Assignment 3 (CILK++)
  • The Cilk++ Page
  • You might find the following information on Cilk++ helpful: Cilk++ Programmer's Guide and the e-Book "How to Survive the Multicore Revolution (or at Least Survive the Hype)".
  • You should have accounts on multi6.aladdin.cs.cmu.edu. Note that the machine has some performance anomalies. If your code is not parallel and runs in under a second you might find it is slower on multiple processors than one.

  • Notes on Assignment 5 (OpenMP)
  • Sun CC compiler's OpenMP docs
  • OpenMP tutorial

  • Tutorial on the Intel Threading Building Blocks (TBB)

  • Notes on Assignment 6 Paper on Linearizability

    • Guy Blelloch, guyb@cs.cmu.edu.